package 中等;

import java.util.Arrays;

public class 数独求解 {

    public static boolean flag = false;

    public static int[][] arr1;

    public static void main(String[] args) {
        int[][] arr = {
                {8, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 3, 6, 0, 0, 0, 0, 0},
                {0, 7, 0, 0, 9, 0, 2, 0, 0},
                {0, 5, 0, 0, 0, 7, 0, 0, 0},
                {0, 0, 0, 0, 4, 5, 7, 0, 0},
                {0, 0, 0, 1, 0, 0, 0, 3, 0},
                {0, 0, 1, 0, 0, 0, 0, 6, 8},
                {0, 0, 8, 5, 0, 0, 0, 1, 0},
                {0, 9, 0, 0, 0, 0, 4, 0, 0}};

        get(arr);
        if (flag){
            for (int[] ints : arr1) {
                System.out.println(Arrays.toString(ints));

            }
        }


    }

    public static void get(int[][] arr){
        if (!isSqrt(arr.length) || !isSqrt(arr[0].length) || arr.length!= arr[0].length){
            System.out.println("数组不合格");
            return;
        }
        set(arr,0 ,0,arr.length );
        if (!flag){
            System.out.println("无解");
        }

    }

    public static boolean isSqrt(int len){
        long sqrt = (long) Math.sqrt(len);
        return sqrt*sqrt==len;
    }

    public static void set(int[][] arr,int x,int y,int n){
        if (flag){
            return;
        }
        if (y==n){
            flag = true;
            arr1 = new int[n][n];
            for (int i = 0; i < arr.length; i++) {
                arr1[i] = arr[i].clone();
            }
            return;
        }
        if (x==n){
            set(arr,0 ,y+1 ,n );
            return;
        }
        if (arr[y][x]!=0){
            set(arr,x+1 ,y ,n );
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (is(arr,x ,y , i)){
                    arr[y][x] = i;
                    set(arr,x+1 ,y , n);
                    arr[y][x] = 0;
            }
        }
    }

    public static boolean is(int[][] arr,int x,int y,int num){
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                //在一行有重复的数字
                if (y==i && arr[i][j] == num){
                    return false;
                }
                //在一列
                if (x==j && arr[i][j] == num){
                    return false;
                }
                //在九宫格
                int sqrt = (int) Math.sqrt(length);
                int X = x/sqrt;
                int Y = y/sqrt;
                if (arr[i][j]==num && (i>=sqrt*Y && i<sqrt*(Y+1)) && (j>=sqrt*X && j<sqrt*(X+1))){
                    return false;
                }
            }
        }
        return true;
    }
}
